package main

func dp(s string) [][]bool {
	res := make([][]bool, len(s)) // res[i][j] 表示，s[i:j+1] 是否为回文串
	for i := range res {
		res[i] = make([]bool, len(s))
	}

	for i := len(s) - 1; i >= 0; i-- {
		for j := 0; j < len(s); j++ {
			if i >= j {
				res[i][j] = true
			} else {
				// i < j
				res[i][j] = res[i+1][j-1] && s[i] == s[j]
			}
		}
	}

	return res
}



func partition(s string) [][]string {
	m := dp(s)
	answers := [][]string{}
	answer := []string{}
	var bfs func(i int)
	bfs = func(i int) {
		if i == len(s) {
			tmp := make([]string, len(answer))
			copy(tmp, answer)
			answers = append(answers, tmp)
			return
		}
		for j := i; j < len(s); j++ {
			if m[i][j] {
				answer = append(answer, s[i:j+1])
				bfs(j+1)
				answer = (answer)[:len(answer)-1]
			}
		}
	}
	bfs(0)
	return answers
}

func main() {
	s := "aabb"
	res := partition(s)
	println(res)
}